package com.ujs.code.Matrix;

import java.util.ArrayList;
import java.util.List;

/**
 * 54. 螺旋矩阵
 * @author zhangshihao
 * @create 2023-09-26 14:18
 */
public class SpiralOrder {
    public static void main(String[] args) {
        SpiralOrder spiralOrder = new SpiralOrder();
        // int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int[][] matrix = {
                {1, 2, 3, 4, 5},
                {6, 7, 8, 9, 10},
                {11, 12, 13, 14, 15},
                {16, 17, 18, 19, 20},
                {21, 22, 23, 24, 25}
        };
        List<Integer> integers = spiralOrder.spiralOrder(matrix);
        System.out.println(integers);
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        int n = Math.min(matrix.length, matrix[0].length);
        int count = matrix.length * matrix[0].length; // 共多少个元素
        int loop = 0; // 控制循环的次数
        int i, j;
        int start = 0; // 每次循环的开始点（start, start）
        while (loop++ < n / 2) {
            for (j = start; j < matrix[0].length - loop; j++) {
                list.add(matrix[start][j]);
                if (list.size() == count) {
                    return list;
                }
            }
            for (i = start; i < matrix.length - loop; i++) {
                list.add(matrix[i][j]);
                if (list.size() == count) {
                    return list;
                }
            }
            for (; j >= loop; j--) {
                list.add(matrix[i][j]);
                if (list.size() == count) {
                    return list;
                }
            }
            for (; i >= loop; i--) {
                list.add(matrix[i][j]);
                if (list.size() == count) {
                    return list;
                }
            }
            start++;
        }
        if (matrix.length == 1 && matrix[0].length == 1) {
            list.add(matrix[0][0]);
            return list;
        }
        if (n % 2 == 1) {
            // 添加中间位置的数字
            list.add(matrix[n / 2][n / 2]);
        }
        return list;
    }
}
